package com.lw.leetcode.back.b;

import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * LCP 41. 黑白翻转棋
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/23 17:07
 */
public class FlipChess {

    public static void main(String[] args) {
        FlipChess test = new FlipChess();

        // 3
//        String[] str = {"....X.", "....X.", "XOOO..", "......", "......"};

        // 7
        String[] str = {"X....", ".O...", "..O..", "..OO.", "XOOO."};

        int i = test.flipChess(str);
        System.out.println(i);
    }

    private int[][] steps = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    private int m;
    private int n;

    public int flipChess(String[] chessboard) {
        m = chessboard.length;
        n = chessboard[0].length();
        int[][] arr = new int[m][n];
        for (int i = 0; i < m; i++) {
            char[] chars = chessboard[i].toCharArray();
            int[] ints = arr[i];
            for (int j = 0; j < n; j++) {
                if (chars[j] == 'X') {
                    ints[j] = 1;
                } else if (chars[j] == 'O') {
                    ints[j] = 2;
                }
            }
        }
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == 0) {
                    arr[i][j] = 1;
                    int[][] copy = copy(arr);
                    int item = find(copy, i, j);
                    max = Math.max(max, item);

                    arr[i][j] = 0;
                }
            }
        }
        return max;
    }

    private int[][] copy(int[][] arr) {
        int[][] copy = new int[m][n];
        for (int i = 0; i < m; i++) {
            System.arraycopy(arr[i], 0, copy[i], 0, n);
        }
        return copy;
    }

    private int find(int[][] arr, int x, int y) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add((x << 4) + y);
        int count = 0;
        while (!list.isEmpty()) {
            int poll = list.poll();
            int a = poll >> 4;
            int b = poll & 0XF;
            for (int[] step : steps) {
                int c = check(arr, a, b, step[0], step[1]);
//                System.out.println(x + "  " + y + "  " +c);
                count += c;
                add(arr, a, b, step[0], step[1], list, c);
            }
        }
        return count;
    }

    private int check(int[][] arr, int x, int y, int s1, int s2) {
        x += s1;
        y += s2;
        int c = 0;
        while (x >= 0 && x < m && y >= 0 && y < n) {
            if (arr[x][y] == 0) {
                return 0;
            }
            if (arr[x][y] == 1) {
                return c;
            }
            c++;
            x += s1;
            y += s2;
        }
        return 0;
    }

    private void add(int[][] arr, int x, int y, int s1, int s2, LinkedList<Integer> list, int c) {
        for (int i = 0; i < c; i++) {
            x += s1;
            y += s2;
            arr[x][y] = 1;
            list.add((x << 4) + y);
        }
    }

}
